package sortStudy;

public class HeapSort {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 1, 7, 9, 4, 6, 8, 3};
        heapSort(nums);
        for (int i = 0; i < nums.length; i++){
            System.out.println(nums[i]);
        }
    }

    public static void heapSort(int[] arr){
        int heapSize = arr.length;
        //对大根堆进行初始化
        buildMaxHeap(arr, heapSize);
        for (int i = arr.length - 1; i > 0 ; i--) {
            swap(arr, 0, i);
            heapSize--;
            maxHeapify(arr, 0, heapSize);
        }
    }
    //进行堆的初始化
    public static void buildMaxHeap(int[] arr, int heapSize){
        for (int i = heapSize/2 - 1; i >= 0; i--){
            maxHeapify(arr, i, heapSize);
        }
    }

    public static void maxHeapify(int[] arr, int i, int heapSize){
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
        if (left < heapSize && arr[left] > arr[largest]){
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]){
            largest = right;
        }
        if (largest != i){
            swap(arr, i, largest);
            maxHeapify(arr, largest, heapSize);
        }
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
